package 我的Java学习_算法基础.day_06;

public class _104_快速幂运算 {
    public static void main(String[] args) {
        for(int i =1;i<10;i++){
            System.out.println(fib(i));
        }
    }
    public static int ex(int a,int n){
        if(n==1)
            return a;
        int temp = a; //a的1次方
        int res = 1;
        int exponent = 1;
        while((exponent<<1)<n){
            temp*=temp;
            exponent<<=1;
        }

        res*=ex(a,n-exponent);
        return res*temp;
    }
    public static long ex2(long n,long m){
        long pingFangShu = n;//n的1次方
        long result = 1;
        while(m!=0){
            if((m&1)==1)
                result *=pingFangShu;
            //每移位一次，幂累乘方一次
            pingFangShu *=pingFangShu;
            //右移一位
            m>>=1;
        }
        return result;
    }
    public static long fib(long n){
        if(n==1||n==2) return 1;
        long[][] matrix = {
                {0,1},
                {1,1}
        };
        long[][] res =matrixPower(matrix,n-1);
        res = matrixMultiply(new long[][]{{1,1}},res);
        return res[0][0];
    }
    public static long[][] matrixPower(long[][] matrix,long p){
        //初始化结果为单位矩阵，对角线为1
        long[][] result = new long[matrix.length][matrix[0].length];
        for(int i = 0;i<result.length;i++){
            result[i][i]=1;
        }

        //平方数
        long[][] pingFang = matrix;//一次方
        for(;p!=0;p>>=1){
            if((p&1)!=0){//当前二进制位最低为1，将当前平方数乘到结果中
                result = matrixMultiply(result,pingFang);
            }
            //平方数继续上翻
            pingFang = matrixMultiply(pingFang,pingFang);
        }
        return result;
    }
    private static long[][] matrixMultiply(long[][] m1,long[][] m2){
        final int n = m1.length;
        final int m = m1[0].length;
        if(m!=m2.length) throw new IllegalArgumentException();
        final int p = m2[0].length;
        long[][] result = new long[n][p];

        for(int i = 0;i<n;i++){
            for(int j =0;j<p;j++){
                for(int k=0;k<m;k++){
                    result[i][j]+=m1[i][k]*m2[k][j];
                }
            }
        }
        return result;
    }
}
